/*
 *  Copyright (c) 2012 Shirou Maruyama
 * 
 *   Redistribution and use in source and binary forms, with or without
 *   modification, are permitted provided that the following conditions
 *   are met:
 * 
 *   1. Redistributions of source code must retain the above Copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above Copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 *   3. Neither the name of the authors nor the names of its contributors
 *      may be used to endorse or promote products derived from this
 *      software without specific prior written permission.
 */

#include <gtest/gtest.h>
#include <sstream>
#include <vector>
#include "HufWatTree.hpp"

using namespace cpi00;
using namespace std;

TEST(HufWatTree, trivial) {
  HufWatTree wt;
  ASSERT_EQ(0ULL, wt.Size());
  ASSERT_EQ(0ULL, wt.Rank('a', 0));

  ostringstream os;
  wt.Write(os);
  
  HufWatTree wt2;
  istringstream is(os.str());
  wt2.Read(is);
  ASSERT_EQ(0ULL, wt2.Size());
  ASSERT_EQ(0ULL, wt2.Rank('a', 0));
}

TEST(HufWatTree, fixed_string) {
  string sample = "acadacacadacabacabadaeafacadabac";
  HufWatTree wt;
  wt.Build(sample);
  ASSERT_EQ((uint64_t)'a', wt.Access(0));
  ASSERT_EQ((uint64_t)'c', wt.Access(sample.size() - 1));
  ASSERT_EQ((uint64_t)'a', wt.Access(10));
  ASSERT_EQ(1ULL,  wt.Rank('a', 0));
  ASSERT_EQ(0ULL,  wt.Rank('d', 0));
  ASSERT_EQ(16ULL, wt.Rank('a', sample.size() - 1));
  ASSERT_EQ(6ULL,  wt.Rank('a', 10));
}

TEST(HufWatTree, random) {
  const uint64_t N = 10000;
  const uint64_t AlphaSize = 64;
  vector<vector<uint64_t> > ranks(AlphaSize);
  string str;
  for (uint64_t i = 0; i < N; ++i) {
    uint64_t x = rand() % AlphaSize;
    str.push_back(x);
    for (uint64_t j = 0; j < AlphaSize; ++j) {
      uint64_t prev = 0;
      if (i > 0) {
        prev = ranks[j][i-1];
      }
      if (j == x) {
        ranks[j].push_back(prev+1);
      }
      else {
        ranks[j].push_back(prev);
      }
    }
  }

  HufWatTree wt;
  wt.Build(str);

  ASSERT_EQ(N, wt.Size());

  for (uint64_t i = 0; i < N; ++i) {
    ASSERT_EQ((uint64_t)str[i], wt.Access(i));
    ASSERT_EQ(ranks[str[i]][i], wt.Rank(str[i], i));
  }

  ostringstream os;
  wt.Write(os);
  wt.Clear();
  ASSERT_EQ(0ULL, wt.Size());
  
  HufWatTree wt2;
  istringstream is(os.str());
  wt2.Read(is);
  ASSERT_EQ(N, wt2.Size());

  for (uint64_t i = 0; i < N; ++i) {
    ASSERT_EQ((uint64_t)str[i], wt2.Access(i));
    ASSERT_EQ(ranks[str[i]][i], wt2.Rank(str[i], i));
  }
}
